문제 설명

XX 모바일 보드게임은 같은 크기의 칸으로 구분된 직선 모양의 게임 보드와 특별한 주사위 3개를 사용해서 진행합니다. 주사위는 각각 1부터 S1, S2, S3까지의 숫자 중 하나가 나오며, 3개의 주사위를 동시에 굴려 나온 숫자의 합만큼 캐릭터를 이동시킵니다. 게임 보드의 몇몇 칸에는 몬스터가 있으므로, 캐릭터는 도착한 칸에서 몬스터를 만나게 될 수도 있습니다. 다음은 S1 = 2, S2 = 3, S3 = 4인 경우의 예시입니다.

image

위 그림에서 별은 캐릭터이며, 붉은 사각형은 몬스터입니다. 캐릭터는 1번 칸에 있습니다. 주사위를 던져 나온 숫자가 1, 1, 2라면 캐릭터는 총 4칸을 이동하여 5번째 칸에 도착해 몬스터를 만납니다. 반면에 주사위를 던져 나온 숫자가 2, 2, 1이라면 총 5칸을 이동한 캐릭터는 6번째 칸에 도착해 몬스터를 만나지 않습니다. 위 예시에서 주사위를 한 번만 굴렸을 때, 주사위 눈의 합만큼 이동해 도착한 칸에서 몬스터를 만나지 않을 확률은 0.5입니다.

몬스터의 위치를 담고 있는 배열 monster와 각 주사위에서 나올 수 있는 최대 숫자 S1, S2, S3가 매개변수로 주어질 때, 1번 칸에 위치한 캐릭터가 주사위를 한 번만 굴려 나온 눈금의 합만큼 이동해서 도착한 칸에 몬스터가 없을 확률을 return 하도록 solution 함수를 완성해 주세요. 단, return 값은 몬스터를 만나지 않을 확률에 1000을 곱한 후 소수부는 버리고 정수 부분만 return 하세요.

제한사항
  • monster는 몬스터의 위치를 담은 배열이며 길이(몬스터의 개수)는 1 이상 99 이하입니다.
  • monster의 각 원소는 현재 몬스터의 위치를 나타내며, 모든 몬스터의 위치는 2 이상 100 이하의 자연수입니다.
  • 같은 위치의 몬스터가 여러 번 중복해서 주어지지 않으며, 한 칸에는 한 마리의 몬스터만 있습니다.

  • 각 주사위를 던져 나올 수 있는 수의 최댓값 S1, S2, S3는 다음과 같습니다.

    • 2 ≤ S1 ≤ 30, 2 ≤ S2 ≤ 30, 2 ≤ S3 ≤ 40, S1, S2, S3는 자연수
  • 몬스터를 만나지 않을 확률에 1000을 곱한 후 소수부는 버리고 정수 부분만 int형으로 return 해주세요.
입출력 예
monster S1 S2 S3 result
[4,9,5,8] 2 3 4 500
[4,9,5,8] 2 3 3 555
입출력 예 설명

입출력 예 #1 몬스터의 위치는 문제에 주어진 예시와 같습니다. 몬스터가 없는 칸에 도착할 확률은 1/2로 0.5이며 1000을 곱한 후 소수부를 버리면 500이 됩니다.

입출력 예 #2 몬스터의 위치는 문제에 주어진 예시와 같습니다. 몬스터가 없는 칸에 도착할 확률은 5/9로 0.55555… 이며 1000을 곱한 후 소수부를 버리면 555가 됩니다.

나의 풀이

첫번째 풀이

소스

def solution(monster, S1, S2, S3):
    all_case = 0
    not_monster_case = 0
    for dice1 in range(1, S1 + 1):
        for dice2 in range(1, S2 + 1):
            for dice3 in range(1, S3 + 1):
                all_case += 1
                if 1 + dice1 + dice2 + dice3 not in monster: # 최대 99
                    not_monster_case += 1
    
    not_monster_percent = not_monster_case / all_case
    
    return int(not_monster_percent * 1000)

설명

  • 문제 이해에 좀 많은 시간을 소비하였는데, 여기에서 확률은 전체 주사위 경우의 수에서 몬스터를 만나지 않을 확률.

  • 아이디어는 다음과 같이 하였음.

      1. 전체 경우의 수 구하기
    • 1번과 동시에 몬스터를 만나지않는 경우의 수 구하기
    • 몬스터를 만나지않는 확률 구하기
    • int(확률 * 1000)
  • 해당 문제로 풀면 다음과 같은 최대 시간복잡도를 갖는다. 최대 29 * 29 * 39 * 99 번 < 3600000 (30x30x40x100)

결과

통과

리뷰

  • 곱집합 조합의 경우 product를 이용할 수 있습니다. :)

    from itertools import product
...
cases = product(range(1, S1 + 1), range(1, S2 + 1), range(1, S3 + 1))
for case in cases:
  all_case += 1
  if sum(case) + 1 not in monster:
      not_monster_case += 1